package reviewAlgorithms.search;

import java.util.HashSet;
import java.util.Set;

public class NumSquares3 {
    public static void main(String[] args) {
        int num = 12;
        System.out.println(numSquares(num));
    }

    private static int numSquares(int num) {
        if (num < 1){
            return 0;
        }
        Set<Integer> square = new HashSet<>();
        for (int i = 1; i * i < num; i++) {
            square.add(i * i);
        }
        int count = 1;
        while (!isDividedBy(num,count,square)){
            count ++;
        }
        return count;
    }

    private static boolean isDividedBy(int num, int count, Set<Integer> square) {
        if (count == 1){
            return square.contains(num);
        }

        for (Integer item : square) {
            if (isDividedBy(num - item,count - 1,square)){
                return true;
            }
        }
        return false;
    }


}
